Data transmission and processing systems that use packet switching for communication between network communication sources and destinations (nodes) in their network often use Link State Packets (LSPs) to facilitate automatic routing for the transmission of data packets between an initial sending node and a destination node to minimize transmission "cost." The cost typically represents a relative delay for transmitting a packet of information in the network. LSPs describe local connectivity of the network as seen by a switch or a link. Unlike system data packets, LSPs carry only data related to routing the data packets throughout the network. Although such routing may be manually programmed, setting up and maintaining network routing tables is a tedious process which is accomplished just as well by a network incorporating LSP routing which has been generally disclosed in the International Organization for Standardization (ISO) Draft International Standard 10589, "Intermediate System to Intermediate System Intra-domain Routing Exchange Protocol For Use in Conjunction With the Protocol for Providing the Connectionless-mode Network Service (ISO 8473)." This document, referred to hereinafter as "ISO 10589" represents the general LSP routing protocol upon which the hereinafter described changes were made in order to create the network routing facility of the present invention. In a network utilizing LSP routing, each "intermediate system" (also referred to as a "switch") in the network ascertains the state of the connections between the switch and other network components. The state of the connections are specified by the channels connected to the switch, the channels connected to a given adjacent link which connects channels, and the cost associated with routing a packet through each channel. The switch then broadcasts that information to all the other switches in the network through an LSP. Each switch in the network maintains in its database the latest LSP received from every other switch in the network and uses this information to compute a table containing information for transferring data between nodes in the network via the switches. This table is referred to hereinafter as a "Forwarding Table."
As implemented in prior art packet switching networks, LSP routing is a poor choice as the routing mechanism for a high-speed extended Local Area Network (LAN) because it cannot prevent the creation of temporary routing loops in network-wide routing. Any time a network topology change occurs, each switch must update is routing information, re-calculate shortest paths between the switch and the ultimate destination node, and transmit the new routing information to the other switches in the network. While the switches are propagating the new routing information throughout the network and re-calculating their Forwarding Tables, there is a possibility that a group of switches possessing inconsistent routing information will guide packets back to a previous sender of the packets, thus creating routing loops.
The detrimental effect of looping packets on network performance has previously been controlled by the addition of a hop-count field to a routing header. A hop-count field is initialized by the creator of the packet to some architectural maximum based upon the greatest number of hops between nodes in the network for routing a packet from the creator node to the destination node of the packet. Each intermediate system, upon receiving the packet, decrements the hop-count before transmitting the packet to the next node on the path to the destination node. If a intermediate system decrements the hop-count to zero and the packet has not yet reached its designated destination, the intermediate system discards the data packet. Thus, data packets are allowed to loop during periods of transition, but are prevented from looping indefinitely.
It is inconvenient, however, to include a hop-count field in a routing header for packets in a high-speed extended LAN because the computational overhead associated with updating the hop-count at each receiving intermediate system (switch) results in a non-negligible decrease in the routing performance of the network.
Also, known LSP routing networks do not ensure that the first intermediate system (switch) to receive and forward a data packet will be on a shortest path from a source endnode (also known as an "endsystem") to a destination endnode. As such, the prior art data packet routing does not guarantee that packets follow the shortest path from the first intermediate system (switch) traversed to the destination endnode.
In known routing protocols, "redirect" packets from switches to endnodes have been implemented. Redirect packets inform the receiving endnode of the proper adjacent switch for receiving a data packet for a particular destination node. The use of redirect packets results in some, but not necessarily all, packets following shortest paths to their respective destinations. In addition, this routing scheme requires additional complexity in the transmission routines executed by the endnodes.
Various schemes for synchronizing network databases have been proposed and implemented, such as "resynch" protocols and their variants. These well known protocols are not self-stabilizing. As a result, they are unable to recover from temporary mis-performance of algorithms by intermediate systems (switches). Furthermore, resynch protocols have never been applied to packet switching networks with broadcast links (i.e. ones capable of transmitting information from a source channel to more than one receiver on a link).
Spanning-tree routing is another well known routing mechanism in which data packets are routed on a single network-wide spanning tree. Spanning-tree routing is self-stabilizing and does not require a packet header, but it does not provide shortest-path routing.